<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 1.2</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 1.2" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 1.2" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-1.xhtml#Chapter-1" rel="prev" title="Chapter 1" />
<link href="1_002e3.xhtml#g_t1_002e3" rel="next" title="1.3" />
<link href="1_002e1.xhtml#g_t1_002e1_002e8" rel="prev" title="1.1.8" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t1_002e2"></a>
<nav class="header">
<p>
Next: <a href="1_002e3.xhtml#g_t1_002e3" accesskey="n" rel="next">1.3</a>, Prev: <a href="1_002e1.xhtml#g_t1_002e1" accesskey="p" rel="prev">1.1</a>, Up: <a href="Chapter-1.xhtml#Chapter-1" accesskey="u" rel="prev">Chapter 1</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Procedures-and-the-Processes-They-Generate"></a>
<h3 class="section"><span class="secnum">1.2</span><span class="sectitle">Procedures and the Processes They Generate</span></h3>

<p>We have now considered the elements of programming: We have used primitive
arithmetic operations, we have combined these operations, and we have
abstracted these composite operations by defining them as compound procedures.
But that is not enough to enable us to say that we know how to program.  Our
situation is analogous to that of someone who has learned the rules for how the
pieces move in chess but knows nothing of typical openings, tactics, or
strategy.  Like the novice chess player, we don’t yet know the common patterns
of usage in the domain.  We lack the knowledge of which moves are worth making
(which procedures are worth defining).  We lack the experience to predict the
consequences of making a move (executing a procedure).
</p>
<p>The ability to visualize the consequences of the actions under consideration is
crucial to becoming an expert programmer, just as it is in any synthetic,
creative activity.  In becoming an expert photographer, for example, one must
learn how to look at a scene and know how dark each region will appear on a
print for each possible choice of exposure and development conditions.  Only
then can one reason backward, planning framing, lighting, exposure, and
development to obtain the desired effects.  So it is with programming, where we
are planning the course of action to be taken by a process and where we control
the process by means of a program.  To become experts, we must learn to
visualize the processes generated by various types of procedures.  Only after
we have developed such a skill can we learn to reliably construct programs that
exhibit the desired behavior.
</p>
<p>A procedure is a pattern for the <a id="index-local-evolution"></a>
<em>local evolution</em> of a computational
process.  It specifies how each stage of the process is built upon the previous
stage.  We would like to be able to make statements about the overall, or
<a id="index-global"></a>
<em>global</em>, behavior of a process whose local evolution has been
specified by a procedure.  This is very difficult to do in general, but we can
at least try to describe some typical patterns of process evolution.
</p>
<p>In this section we will examine some common “shapes” for processes generated
by simple procedures.  We will also investigate the rates at which these
processes consume the important computational resources of time and space.  The
procedures we will consider are very simple.  Their role is like that played by
test patterns in photography: as oversimplified prototypical patterns, rather
than practical examples in their own right.
</p>

<a id="g_t1_002e2_002e1"></a>
<a id="Linear-Recursion-and-Iteration"></a>
<h4 class="subsection"><span class="secnum">1.2.1</span><span class="sectitle">Linear Recursion and Iteration</span></h4>

<p>We begin by considering the factorial function, defined by

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>n</mi>
  <mo>!</mo>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>⋅<!-- ⋅ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>⋯<!-- ⋯ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>2</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>1.</mn>
  </mrow>
</math>

There are many ways to compute factorials.  One way is to make use of the
observation that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> is equal to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> times <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math> for any positive
integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>:

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>n</mi>
  <mo>!</mo>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">[</mo>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>⋅<!-- ⋅ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>⋯<!-- ⋯ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>2</mn>
    <mo>⋅<!-- ⋅ --></mo>
    <mn>1</mn>
    <mo stretchy="false">]</mo>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
    <mo>.</mo>
  </mrow>
</math>

Thus, we can compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> by computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math> and multiplying the
result by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  If we add the stipulation that 1! is equal to 1, this
observation translates directly into a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">1</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>We can use the substitution model of <a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a> to watch this
procedure in action computing 6!, as shown in <a href="#Figure-1_002e3">Figure 1.3</a>.
</p>
<figure class="float">
<a id="Figure-1_002e3"></a>
<object style="width: 52.58ex; height: 31.43ex;" data="fig/chap1/Fig1.3d.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 1.3:</strong> A linear recursive process for computing 6!.</p>
</figcaption>
</figure>

<p>Now let’s take a different perspective on computing factorials.  We could
describe a rule for computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> by specifying that we first multiply 1 by
2, then multiply the result by 3, then by 4, and so on until we reach <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.
More formally, we maintain a running product, together with a counter that
counts from 1 up to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  We can describe the computation by saying that the
counter and the product simultaneously change from one step to the next
according to the rule
</p>
<div class="example">
<pre class="example">product <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">←<!-- ← --></mo>
</math> counter * product
counter <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">←<!-- ← --></mo>
</math> counter + 1
</pre></div>

<p>and stipulating that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> is the value of the product when the counter
exceeds <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.
</p>
<p>Once again, we can recast our description as a procedure for computing
factorials:<a class="footnote_link" id="DOCF29" href="#FOOT29"><sup>29</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">fact-iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fact-iter product counter max-count</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter max-count</span><span class="clo">)</span><span class="pln">
      product
      </span><span class="opn">(</span><span class="pln">fact-iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                 max-count</span><span class="clo">)))</span></pre></div>

<p>As before, we can use the substitution model to visualize the process of
computing 6!, as shown in <a href="#Figure-1_002e4">Figure 1.4</a>.
</p>
<figure class="float">
<a id="Figure-1_002e4"></a>
<object style="width: 23.40ex; height: 23.31ex;" data="fig/chap1/Fig1.4d.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 1.4:</strong> A linear iterative process for computing 6!.</p>
</figcaption>
</figure>

<p>Compare the two processes.  From one point of view, they seem hardly different
at all.  Both compute the same mathematical function on the same domain, and
each requires a number of steps proportional to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>.
Indeed, both processes even carry out the same sequence of multiplications,
obtaining the same sequence of partial products.  On the other hand, when we
consider the “shapes” of the two processes, we find that they evolve quite
differently.
</p>
<p>Consider the first process.  The substitution model reveals a shape of
expansion followed by contraction, indicated by the arrow in <a href="#Figure-1_002e3">Figure 1.3</a>.
The expansion occurs as the process builds up a chain of <a id="index-deferred-operations"></a>
<em>deferred operations</em> 
(in this case, a chain of multiplications).  The contraction occurs
as the operations are actually performed.  This type of process, characterized
by a chain of deferred operations, is called a <a id="index-recursive-process"></a>
<em>recursive process</em>.
Carrying out this process requires that the interpreter keep track of the
operations to be performed later on.  In the computation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>, the length
of the chain of deferred multiplications, and hence the amount of information
needed to keep track of it, grows linearly with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> (is proportional to
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>), just like the number of steps.  Such a process is called a
<a id="index-linear-recursive-process"></a>
<em>linear recursive process</em>.
</p>
<p>By contrast, the second process does not grow and shrink.  At each step, all we
need to keep track of, for any <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, are the current values of the variables
<code>product</code>, <code>counter</code>, and <code>max-count</code>.  We call this an
<a id="index-iterative-process"></a>
<em>iterative process</em>.  In general, an iterative process is one whose
state can be summarized by a fixed number of <a id="index-state-variables"></a>
<em>state variables</em>,
together with a fixed rule that describes how the state variables should be
updated as the process moves from state to state and an (optional) end test
that specifies conditions under which the process should terminate.  In
computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>, the number of steps required grows linearly with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Such
a process is called a <a id="index-linear-iterative-process"></a>
<em>linear iterative process</em>.
</p>
<p>The contrast between the two processes can be seen in another way.  In the
iterative case, the program variables provide a complete description of the
state of the process at any point.  If we stopped the computation between
steps, all we would need to do to resume the computation is to supply the
interpreter with the values of the three program variables.  Not so with the
recursive process.  In this case there is some additional “hidden”
information, maintained by the interpreter and not contained in the program
variables, which indicates “where the process is” in negotiating the chain of
deferred operations.  The longer the chain, the more information must be
maintained.<a class="footnote_link" id="DOCF30" href="#FOOT30"><sup>30</sup></a>
</p>
<p>In contrasting iteration and recursion, we must be careful not to confuse the
notion of a recursive <a id="index-process"></a>
<em>process</em> with the notion of a recursive
<a id="index-procedure"></a>
<em>procedure</em>.  When we describe a procedure as recursive, we are
referring to the syntactic fact that the procedure definition refers (either
directly or indirectly) to the procedure itself.  But when we describe a
process as following a pattern that is, say, linearly recursive, we are
speaking about how the process evolves, not about the syntax of how a procedure
is written.  It may seem disturbing that we refer to a recursive procedure such
as <code>fact-iter</code> as generating an iterative process.  However, the process
really is iterative: Its state is captured completely by its three state
variables, and an interpreter need keep track of only three variables in order
to execute the process.
</p>
<p>One reason that the distinction between process and procedure may be confusing
is that most implementations of common languages (including Ada, Pascal, and C)
are designed in such a way that the interpretation of any recursive procedure
consumes an amount of memory that grows with the number of procedure calls,
even when the process described is, in principle, iterative.  As a consequence,
these languages can describe iterative processes only by resorting to
special-purpose “looping constructs” such as <code>do</code>, <code>repeat</code>,
<code>until</code>, <code>for</code>, and <code>while</code>.  The implementation of Scheme we
shall consider in <a href="Chapter-5.xhtml#Chapter-5">Chapter 5</a> does not share this defect.  It will execute
an iterative process in constant space, even if the iterative process is
described by a recursive procedure.  An implementation with this property is
called <a id="index-tail_002drecursive"></a>
<em>tail-recursive</em>.  With a tail-recursive implementation,
iteration can be expressed using the ordinary procedure call mechanism, so that
special iteration constructs are useful only as syntactic sugar.<a class="footnote_link" id="DOCF31" href="#FOOT31"><sup>31</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e9"></a>Exercise 1.9:</strong> Each of the following two
procedures defines a method for adding two positive integers in terms of the
procedures <code>inc</code>, which increments its argument by 1, and <code>dec</code>,
which decrements its argument by 1.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> a </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
      b 
      </span><span class="opn">(</span><span class="pln">inc </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dec a</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> a </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
      b 
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">dec a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inc b</span><span class="clo">))))</span></pre></div>

<p>Using the substitution model, illustrate the process generated by each
procedure in evaluating <code>(+ 4 5)</code>.  Are these processes iterative or
recursive?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e10"></a>Exercise 1.10:</strong> The following procedure computes
a mathematical function called Ackermann’s function.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">A x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> y </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> x </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> y</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> y </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">A </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">A x </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> y </span><span class="lit">1</span><span class="clo">))))))</span></pre></div>

<p>What are the values of the following expressions?
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">A </span><span class="lit">1</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">A </span><span class="lit">2</span><span class="pln"> </span><span class="lit">4</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">A </span><span class="lit">3</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span></pre></div>

<p>Consider the following procedures, where <code>A</code> is the procedure
defined above:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">A </span><span class="lit">0</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">A </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">h n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">A </span><span class="lit">2</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">k n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">5</span><span class="pln"> n n</span><span class="clo">))</span></pre></div>

<p>Give concise mathematical definitions for the functions computed by the
procedures <code>f</code>, <code>g</code>, and <code>h</code> for positive integer values of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  For example, <code>(k n)</code> computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>5</mn>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.
</p></blockquote>

<a id="g_t1_002e2_002e2"></a>
<a id="Tree-Recursion"></a>
<h4 class="subsection"><span class="secnum">1.2.2</span><span class="sectitle">Tree Recursion</span></h4>

<p>Another common pattern of computation is called <a id="index-tree-recursion"></a>
<em>tree recursion</em>.  As
an example, consider computing the sequence of Fibonacci numbers, in which each
number is the sum of the preceding two:
</p>
<div style="text-align: center">0, 1, 1, 2, 3, 5, 8, 13, 21, ….
</div>
<p>In general, the Fibonacci numbers can be defined by the rule

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtext>Fib</mtext>
  <mo stretchy="false">(</mo>
  <mi>n</mi>
  <mo stretchy="false">)</mo>
  <mspace width="thickmathspace"/>
  <mo>=</mo>
  <mspace width="thickmathspace"/>
  <mrow>
    <mo>{</mo>
    <mtable columnalign="left left" rowspacing="4pt" columnspacing="1em">
      <mtr>
        <mtd>
          <mn>0</mn>
        </mtd>
        <mtd>
          <mspace width="thickmathspace"/>
          <mtext>if</mtext>
          <mspace width="thickmathspace"/>
          <mspace width="thickmathspace"/>
          <mi>n</mi>
          <mo>=</mo>
          <mn>0</mn>
          <mo>,</mo>
        </mtd>
      </mtr>
      <mtr>
        <mtd>
          <mn>1</mn>
        </mtd>
        <mtd>
          <mspace width="thickmathspace"/>
          <mtext>if</mtext>
          <mspace width="thickmathspace"/>
          <mspace width="thickmathspace"/>
          <mi>n</mi>
          <mo>=</mo>
          <mn>1</mn>
          <mo>,</mo>
        </mtd>
      </mtr>
      <mtr>
        <mtd>
          <mtext>Fib</mtext>
          <mo stretchy="false">(</mo>
          <mi>n</mi>
          <mo>−<!-- − --></mo>
          <mn>1</mn>
          <mo stretchy="false">)</mo>
          <mo>+</mo>
          <mtext>Fib</mtext>
          <mo stretchy="false">(</mo>
          <mi>n</mi>
          <mo>−<!-- − --></mo>
          <mn>2</mn>
          <mo stretchy="false">)</mo>
        </mtd>
        <mtd>
          <mspace width="thickmathspace"/>
          <mtext>otherwise</mtext>
          <mo>.</mo>
        </mtd>
      </mtr>
    </mtable>
  </mrow>
</math>

We can immediately translate this definition into a recursive procedure for
computing Fibonacci numbers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">))))))</span></pre></div>

<p>Consider the pattern of this computation.  To compute <code>(fib 5)</code>, we
compute <code>(fib 4)</code> and <code>(fib 3)</code>.  To compute <code>(fib 4)</code>, we
compute <code>(fib 3)</code> and <code>(fib 2)</code>.  In general, the evolved process
looks like a tree, as shown in <a href="#Figure-1_002e5">Figure 1.5</a>.  Notice that the branches
split into two at each level (except at the bottom); this reflects the fact
that the <code>fib</code> procedure calls itself twice each time it is invoked.
</p>
<figure class="float">
<a id="Figure-1_002e5"></a>
<object style="width: 58.07ex; height: 36.18ex;" data="fig/chap1/Fig1.5d.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 1.5:</strong> The tree-recursive process generated in computing <code>(fib 5)</code>.</p>
</figcaption>
</figure>

<p>This procedure is instructive as a prototypical tree recursion, but it is a
terrible way to compute Fibonacci numbers because it does so much redundant
computation.  Notice in <a href="#Figure-1_002e5">Figure 1.5</a> that the entire computation of
<code>(fib 3)</code>—almost half the work—is duplicated.  In fact, it is not hard
to show that the number of times the procedure will compute <code>(fib 1)</code> or
<code>(fib 0)</code> (the number of leaves in the above tree, in general) is
precisely <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  To get an idea of how bad this is, one can
show that the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> grows exponentially with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  More
precisely (see <a href="#Exercise-1_002e13">Exercise 1.13</a>), <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is the closest integer
to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>φ<!-- φ --></mi>
      <mi>n</mi>
    </msup>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msqrt>
      <mn>5</mn>
    </msqrt>
  </mrow>
</math>, where

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>φ<!-- φ --></mi>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mfrac>
    <mrow>
      <mn>1</mn>
      <mo>+</mo>
      <msqrt>
        <mn>5</mn>
      </msqrt>
    </mrow>
    <mn>2</mn>
  </mfrac>
  <mspace width="thinmathspace"/>
  <mo>≈<!-- ≈ --></mo>
  <mspace width="thinmathspace"/>
  <mn>1.6180</mn>
</math>

is the <a id="index-golden-ratio"></a>
<em>golden ratio</em>, which satisfies the equation

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <msup>
    <mi>φ<!-- φ --></mi>
    <mn>2</mn>
  </msup>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>φ<!-- φ --></mi>
    <mo>+</mo>
    <mn>1.</mn>
  </mrow>
</math>

Thus, the process uses a number of steps that grows exponentially with the
input.  On the other hand, the space required grows only linearly with the
input, because we need keep track only of which nodes are above us in the tree
at any point in the computation.  In general, the number of steps required by a
tree-recursive process will be proportional to the number of nodes in the tree,
while the space required will be proportional to the maximum depth of the tree.
</p>
<p>We can also formulate an iterative process for computing the Fibonacci numbers.
The idea is to use a pair of integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, initialized to
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib(1) = 1</mtext>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib(0) = 0</mtext>
  </mrow>
</math>, and to repeatedly apply the
simultaneous transformations
</p>

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="left" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <mi>a</mi>
        <mspace width="thickmathspace"/>
        <mo stretchy="false">←<!-- ← --></mo>
        <mspace width="thickmathspace"/>
        <mi>a</mi>
        <mo>+</mo>
        <mi>b</mi>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>b</mi>
        <mspace width="thickmathspace"/>
        <mo stretchy="false">←<!-- ← --></mo>
        <mspace width="thickmathspace"/>
        <mi>a</mi>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>

<p>It is not hard to show that, after applying this transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> times,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> will be equal, respectively, to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  Thus, we can compute Fibonacci numbers iteratively using
the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">fib-iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib-iter a b count</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> count </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      b
      </span><span class="opn">(</span><span class="pln">fib-iter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> count </span><span class="lit">1</span><span class="clo">))))</span></pre></div>

<p>This second method for computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is a linear iteration.  The
difference in number of steps required by the two methods—one linear in
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, one growing as fast as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> itself—is enormous, even for
small inputs.
</p>
<p>One should not conclude from this that tree-recursive processes are useless.
When we consider processes that operate on hierarchically structured data
rather than numbers, we will find that tree recursion is a natural and powerful
tool.<a class="footnote_link" id="DOCF32" href="#FOOT32"><sup>32</sup></a> But
even in numerical operations, tree-recursive processes can be useful in helping
us to understand and design programs.  For instance, although the first
<code>fib</code> procedure is much less efficient than the second one, it is more
straightforward, being little more than a translation into Lisp of the
definition of the Fibonacci sequence.  To formulate the iterative algorithm
required noticing that the computation could be recast as an iteration with
three state variables.
</p>
<a id="Example_003a-Counting-change"></a>
<h5 class="subsubheading">Example: Counting change</h5>

<p>It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm.  In contrast, consider the following problem: How many different
ways can we make change of $1.00, given half-dollars, quarters, dimes,
nickels, and pennies?  More generally, can we write a procedure to compute the
number of ways to change any given amount of money?
</p>
<p>This problem has a simple solution as a recursive procedure.  Suppose we think
of the types of coins available as arranged in some order.  Then the following
relation holds:
</p>
<p>The number of ways to change amount <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> using <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> kinds of coins equals
</p>
<ul>
<li> the number of ways to change amount <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> using all but the first kind of coin,
plus

</li><li> the number of ways to change amount <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>−<!-- − --></mo>
    <mi>d</mi>
  </mrow>
</math> using all <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> kinds of
coins, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math> is the denomination of the first kind of coin.

</li></ul>

<p>To see why this is true, observe that the ways to make change can be divided
into two groups: those that do not use any of the first kind of coin, and those
that do.  Therefore, the total number of ways to make change for some amount is
equal to the number of ways to make change for the amount without using any of
the first kind of coin, plus the number of ways to make change assuming that we
do use the first kind of coin.  But the latter number is equal to the number of
ways to make change for the amount that remains after using a coin of the first
kind.
</p>
<p>Thus, we can recursively reduce the problem of changing a given amount to the
problem of changing smaller amounts using fewer kinds of coins.  Consider this
reduction rule carefully, and convince yourself that we can use it to describe
an algorithm if we specify the following degenerate cases:<a class="footnote_link" id="DOCF33" href="#FOOT33"><sup>33</sup></a>
</p>
<ul>
<li> If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is exactly 0, we should count that as 1 way to make change.

</li><li> If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is less than 0, we should count that as 0 ways to make change.

</li><li> If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is 0, we should count that as 0 ways to make change.

</li></ul>

<p>We can easily translate this description into a recursive procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">count-change amount</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cc amount </span><span class="lit">5</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cc amount kinds-of-coins</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> amount </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="kwd">or</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> amount </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">0</span><span class="clo">))</span><span class="pln"> 
         </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cc amount </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> kinds-of-coins </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">cc </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> amount </span><span class="opn">(</span><span class="pln">first-denomination 
                           kinds-of-coins</span><span class="clo">))</span><span class="pln">
                kinds-of-coins</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-denomination kinds-of-coins</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">3</span><span class="clo">)</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> </span><span class="lit">25</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> kinds-of-coins </span><span class="lit">5</span><span class="clo">)</span><span class="pln"> </span><span class="lit">50</span><span class="clo">)))</span></pre></div>

<p>(The <code>first-denomination</code> procedure takes as input the number of kinds of
coins available and returns the denomination of the first kind.  Here we are
thinking of the coins as arranged in order from largest to smallest, but any
order would do as well.)  We can now answer our original question about
changing a dollar:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">count-change </span><span class="lit">100</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">292</span></i>
</pre></div>

<p><code>Count-change</code> generates a tree-recursive process with redundancies
similar to those in our first implementation of <code>fib</code>.  (It will take
quite a while for that 292 to be computed.)  On the other hand, it is not
obvious how to design a better algorithm for computing the result, and we leave
this problem as a challenge.  The observation that a tree-recursive process may
be highly inefficient but often easy to specify and understand has led people
to propose that one could get the best of both worlds by designing a “smart
compiler” that could transform tree-recursive procedures into more efficient
procedures that compute the same result.<a class="footnote_link" id="DOCF34" href="#FOOT34"><sup>34</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e11"></a>Exercise 1.11:</strong> A function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is defined by
the rule that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mi>n</mi>
  </mrow>
</math> if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>&lt;</mo>
    <mn>3</mn>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>3</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>≥<!-- ≥ --></mo>
    <mn>3</mn>
  </mrow>
</math>.  
Write a procedure that computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> by means of a recursive process.  Write a procedure that
computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> by means of an iterative process.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e12"></a>Exercise 1.12:</strong> The following pattern of numbers
is called <a id="index-Pascal_0027s-triangle"></a>
<em>Pascal’s triangle</em>.
</p>
<div class="example">
<pre class="example">         1
       1   1
     1   2   1
   1   3   3   1
 1   4   6   4   1
       . . .
</pre></div>

<p>The numbers at the edge of the triangle are all 1, and each number inside the
triangle is the sum of the two numbers above it.<a class="footnote_link" id="DOCF35" href="#FOOT35"><sup>35</sup></a> Write a procedure that computes elements of Pascal’s triangle by
means of a recursive process.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e13"></a>Exercise 1.13:</strong> Prove that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is
the closest integer to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>φ<!-- φ --></mi>
      <mi>n</mi>
    </msup>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msqrt>
      <mn>5</mn>
    </msqrt>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>+</mo>
    <msqrt>
      <mn>5</mn>
    </msqrt>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>.  
Hint: Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>ψ<!-- ψ --></mi>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>−<!-- − --></mo>
    <msqrt>
      <mn>5</mn>
    </msqrt>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>2</mn>
  </mrow>
</math>.
Use induction and the definition of the Fibonacci numbers (see <a href="#g_t1_002e2_002e2">1.2.2</a>) 
to prove that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>φ<!-- φ --></mi>
      <mi>n</mi>
    </msup>
    <mo>−<!-- − --></mo>
    <msup>
      <mi>ψ<!-- ψ --></mi>
      <mi>n</mi>
    </msup>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msqrt>
      <mn>5</mn>
    </msqrt>
  </mrow>
</math>.
</p></blockquote>

<a id="g_t1_002e2_002e3"></a>
<a id="Orders-of-Growth"></a>
<h4 class="subsection"><span class="secnum">1.2.3</span><span class="sectitle">Orders of Growth</span></h4>

<p>The previous examples illustrate that processes can differ considerably in the
rates at which they consume computational resources.  One convenient way to
describe this difference is to use the notion of <a id="index-order-of-growth"></a>
<em>order of growth</em> to
obtain a gross measure of the resources required by a process as the inputs
become larger.
</p>
<p>Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> be a parameter that measures the size of the problem, and let
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> be the amount of resources the process requires for a problem of
size <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  In our previous examples we took <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to be the number for which
a given function is to be computed, but there are other possibilities.  For
instance, if our goal is to compute an approximation to the square root of a
number, we might take <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to be the number of digits accuracy required.  For
matrix multiplication we might take <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to be the number of rows in the
matrices.  In general there are a number of properties of the problem with
respect to which it will be desirable to analyze a given process.  Similarly,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> might measure the number of internal storage registers used, the
number of elementary machine operations performed, and so on.  In computers
that do only a fixed number of operations at a time, the time required will be
proportional to the number of elementary machine operations performed.
</p>
<p>We say that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> has order of growth <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, written
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math> (pronounced “theta of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>”), if there are positive constants <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>k</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>k</mi>
    <mn>2</mn>
  </msub>
</math>
independent of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>k</mi>
      <mn>1</mn>
    </msub>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>≤<!-- ≤ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>≤<!-- ≤ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>k</mi>
      <mn>2</mn>
    </msub>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> 
for any sufficiently large value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  (In other words, for large <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>,
the value <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>R</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is sandwiched between <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>k</mi>
      <mn>1</mn>
    </msub>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>k</mi>
      <mn>2</mn>
    </msub>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.)
</p>
<p>For instance, with the linear recursive process for computing factorial
described in <a href="#g_t1_002e2_002e1">1.2.1</a> the number of steps grows proportionally to
the input <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Thus, the steps required for this process grows as
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  We also saw that the space required grows as
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  For the iterative factorial, the number of steps is still
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> but the space is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>—that is,
constant.<a class="footnote_link" id="DOCF36" href="#FOOT36"><sup>36</sup></a> The
tree-recursive Fibonacci computation requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>φ<!-- φ --></mi>
      <mi>n</mi>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
steps and space <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
</math> is the golden ratio
described in <a href="#g_t1_002e2_002e2">1.2.2</a>.
</p>
<p>Orders of growth provide only a crude description of the behavior of a process.
For example, a process requiring <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mn>2</mn>
  </msup>
</math> steps and a process requiring
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1000</mn>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math> steps and a process requiring <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>10</mn>
    <mi>n</mi>
  </mrow>
  <mo>+</mo>
  <mn>17</mn>
</math> steps all
have <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>n</mi>
      <mn>2</mn>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math> order of growth.  On the other hand, order of growth
provides a useful indication of how we may expect the behavior of the process
to change as we change the size of the problem.  For a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
(linear) process, doubling the size will roughly double the amount of resources
used.  For an exponential process, each increment in problem size will multiply
the resource utilization by a constant factor.  In the remainder of 
<a href="#g_t1_002e2">1.2</a> we will examine two algorithms whose order of growth is logarithmic,
so that doubling the problem size increases the resource requirement by a
constant amount.
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e14"></a>Exercise 1.14:</strong> Draw the tree illustrating the
process generated by the <code>count-change</code> procedure of <a href="#g_t1_002e2_002e2">1.2.2</a>
in making change for 11 cents.  What are the orders of growth of the space and
number of steps used by this process as the amount to be changed increases?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e15"></a>Exercise 1.15:</strong> The sine of an angle (specified
in radians) can be computed by making use of the approximation 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
    <mo>≈<!-- ≈ --></mo>
    <mi>x</mi>
  </mrow>
</math> if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is sufficiently small, and the trigonometric
identity

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mfrac>
      <mi>x</mi>
      <mn>3</mn>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>−<!-- − --></mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <msup>
      <mi>sin</mi>
      <mn>3</mn>
    </msup>
    <mo>⁡<!-- ⁡ --></mo>
    <mfrac>
      <mi>x</mi>
      <mn>3</mn>
    </mfrac>
  </mrow>
</math>

to reduce the size of the argument of sin.  (For purposes of this
exercise an angle is considered “sufficiently small” if its magnitude is not
greater than 0.1 radians.) These ideas are incorporated in the following
procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube x</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sine angle</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs angle</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0.1</span><span class="clo">))</span><span class="pln">
       angle
       </span><span class="opn">(</span><span class="pln">p </span><span class="opn">(</span><span class="pln">sine </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> angle </span><span class="lit">3.0</span><span class="clo">)))))</span></pre></div>

<ol>
<li> How many times is the procedure <code>p</code> applied when <code>(sine 12.15)</code> is
evaluated?

</li><li> What is the order of growth in space and number of steps (as a function of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>) used by the process generated by the <code>sine</code> procedure when
<code>(sine a)</code> is evaluated?

</li></ol>
</blockquote>

<a id="g_t1_002e2_002e4"></a>
<a id="Exponentiation"></a>
<h4 class="subsection"><span class="secnum">1.2.4</span><span class="sectitle">Exponentiation</span></h4>

<p>Consider the problem of computing the exponential of a given number.  We would
like a procedure that takes as arguments a base <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> and a positive integer
exponent <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>b</mi>
    <mi>n</mi>
  </msup>
</math>.  One way to do this is via the
recursive definition

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="left" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mi>n</mi>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <mi>b</mi>
        <mo>⋅<!-- ⋅ --></mo>
        <msup>
          <mi>b</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>n</mi>
            <mo>−<!-- − --></mo>
            <mn>1</mn>
          </mrow>
        </msup>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mn>0</mn>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
  </mtable>
</math>

which translates readily into the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt b n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">1</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b </span><span class="opn">(</span><span class="pln">expt b </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>This is a linear recursive process, which requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> space.  Just as with factorial, we can readily formulate an
equivalent linear iteration:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt b n</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">expt-iter b n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt-iter b counter product</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> counter </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      product
      </span><span class="opn">(</span><span class="pln">expt-iter b
                 </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b product</span><span class="clo">))))</span></pre></div>

<p>This version requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> steps and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> space.
</p>
<p>We can compute exponentials in fewer steps by using successive squaring.  For
instance, rather than computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>b</mi>
    <mn>8</mn>
  </msup>
</math> as

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>b</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
  </mrow>
  <mo>⋅<!-- ⋅ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
  </mrow>
  <mo>⋅<!-- ⋅ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo>⋅<!-- ⋅ --></mo>
    <mi>b</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
</math>

we can compute it using three multiplications:

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="left" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mn>2</mn>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <mi>b</mi>
        <mo>⋅<!-- ⋅ --></mo>
        <mi>b</mi>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mn>4</mn>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <msup>
          <mi>b</mi>
          <mn>2</mn>
        </msup>
        <mo>⋅<!-- ⋅ --></mo>
        <msup>
          <mi>b</mi>
          <mn>2</mn>
        </msup>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mn>8</mn>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <msup>
          <mi>b</mi>
          <mn>4</mn>
        </msup>
        <mo>⋅<!-- ⋅ --></mo>
        <msup>
          <mi>b</mi>
          <mn>4</mn>
        </msup>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>

This method works fine for exponents that are powers of 2.  We can also take
advantage of successive squaring in computing exponentials in general if we use
the rule

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="left left" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mi>n</mi>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <mo stretchy="false">(</mo>
        <msup>
          <mi>b</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>n</mi>
            <mrow class="MJX-TeXAtom-ORD">
              <mo>/</mo>
            </mrow>
            <mn>2</mn>
          </mrow>
        </msup>
        <msup>
          <mo stretchy="false">)</mo>
          <mn>2</mn>
        </msup>
      </mtd>
      <mtd>
        <mtext>if</mtext>
        <mspace width="thickmathspace"/>
        <mi>n</mi>
        <mspace width="thickmathspace"/>
        <mtext>is even</mtext>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msup>
          <mi>b</mi>
          <mi>n</mi>
        </msup>
        <mspace width="thinmathspace"/>
        <mo>=</mo>
        <mspace width="thinmathspace"/>
        <mi>b</mi>
        <mo>⋅<!-- ⋅ --></mo>
        <msup>
          <mi>b</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mi>n</mi>
            <mo>−<!-- − --></mo>
            <mn>1</mn>
          </mrow>
        </msup>
      </mtd>
      <mtd>
        <mtext>if</mtext>
        <mspace width="thickmathspace"/>
        <mi>n</mi>
        <mspace width="thickmathspace"/>
        <mtext>is odd</mtext>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>

We can express this method as a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fast-expt b n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
         </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">even? n</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">square </span><span class="opn">(</span><span class="pln">fast-expt b </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b </span><span class="opn">(</span><span class="pln">fast-expt b </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))))</span></pre></div>

<p>where the predicate to test whether an integer is even is defined in terms of
the primitive procedure <code>remainder</code> by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">even? n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remainder n </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>The process evolved by <code>fast-expt</code> grows logarithmically with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> in
both space and number of steps.  To see this, observe that computing
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mn>2</mn>
      <mi>n</mi>
    </mrow>
  </msup>
</math> using <code>fast-expt</code> requires only one more multiplication
than computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>b</mi>
    <mi>n</mi>
  </msup>
</math>.  The size of the exponent we can compute therefore
doubles (approximately) with every new multiplication we are allowed.  Thus,
the number of multiplications required for an exponent of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> grows about as
fast as the logarithm of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to the base 2.  The process has
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> growth.<a class="footnote_link" id="DOCF37" href="#FOOT37"><sup>37</sup></a>
</p>
<p>The difference between <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> growth and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> growth becomes striking as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> becomes large.  For
example, <code>fast-expt</code> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> = 1000 requires only 14
multiplications.<a class="footnote_link" id="DOCF38" href="#FOOT38"><sup>38</sup></a> It is also possible to
use the idea of successive squaring to devise an iterative algorithm that
computes exponentials with a logarithmic number of steps (see <a href="#Exercise-1_002e16">Exercise 1.16</a>), 
although, as is often the case with iterative algorithms, this is not
written down so straightforwardly as the recursive algorithm.<a class="footnote_link" id="DOCF39" href="#FOOT39"><sup>39</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e16"></a>Exercise 1.16:</strong> Design a procedure that evolves
an iterative exponentiation process that uses successive squaring and uses a
logarithmic number of steps, as does <code>fast-expt</code>.  (Hint: Using the
observation that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mo>/</mo>
        </mrow>
        <mn>2</mn>
      </mrow>
    </msup>
    <msup>
      <mo stretchy="false">)</mo>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>b</mi>
      <mn>2</mn>
    </msup>
    <msup>
      <mo stretchy="false">)</mo>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mrow class="MJX-TeXAtom-ORD">
          <mo>/</mo>
        </mrow>
        <mn>2</mn>
      </mrow>
    </msup>
  </mrow>
</math>, keep, along with
the exponent <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and the base <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, an additional state variable <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, and
define the state transformation in such a way that the product <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <msup>
      <mi>b</mi>
      <mi>n</mi>
    </msup>
  </mrow>
</math> 
is unchanged from state to state.  At the beginning of the process
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is taken to be 1, and the answer is given by the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> at the
end of the process.  In general, the technique of defining an
<a id="index-invariant-quantity"></a>
<em>invariant quantity</em> that remains unchanged from state to state is a
powerful way to think about the design of iterative algorithms.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e17"></a>Exercise 1.17:</strong> The exponentiation algorithms in
this section are based on performing exponentiation by means of repeated
multiplication.  In a similar way, one can perform integer multiplication by
means of repeated addition.  The following multiplication procedure (in which
it is assumed that our language can only add, not multiply) is analogous to the
<code>expt</code> procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> b </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> b </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>This algorithm takes a number of steps that is linear in <code>b</code>.  Now suppose
we include, together with addition, operations <code>double</code>, which doubles an
integer, and <code>halve</code>, which divides an (even) integer by 2.  Using these,
design a multiplication procedure analogous to <code>fast-expt</code> that uses a
logarithmic number of steps.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e18"></a>Exercise 1.18:</strong> Using the results of
<a href="#Exercise-1_002e16">Exercise 1.16</a> and <a href="#Exercise-1_002e17">Exercise 1.17</a>, devise a procedure that generates
an iterative process for multiplying two integers in terms of adding, doubling,
and halving and uses a logarithmic number of steps.<a class="footnote_link" id="DOCF40" href="#FOOT40"><sup>40</sup></a>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e19"></a>Exercise 1.19:</strong> There is a clever algorithm for
computing the Fibonacci numbers in a logarithmic number of steps.  Recall the
transformation of the state variables <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> in the <code>fib-iter</code>
process of <a href="#g_t1_002e2_002e2">1.2.2</a>: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
  <mo stretchy="false">←<!-- ← --></mo>
  <mi>a</mi>
  <mo>+</mo>
  <mi>b</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
  <mo stretchy="false">←<!-- ← --></mo>
  <mi>a</mi>
</math>.
Call this transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math>, and observe that applying <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math> over and over
again <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> times, starting with 1 and 0, produces the pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  In other words, the Fibonacci numbers are produced
by applying <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>T</mi>
    <mi>n</mi>
  </msup>
</math>, the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> power of the transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math>,
starting with the pair (1, 0).  Now consider <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math> to be the special case of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>p</mi>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>q</mi>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math> in a family of transformations <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>T</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>p</mi>
      <mi>q</mi>
    </mrow>
  </msub>
</math>,
where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>T</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>p</mi>
      <mi>q</mi>
    </mrow>
  </msub>
</math> transforms the pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo>,</mo>
    <mi>b</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> according to 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
  <mo stretchy="false">←<!-- ← --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>b</mi>
    <mi>q</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>q</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>p</mi>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
  <mo stretchy="false">←<!-- ← --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>b</mi>
    <mi>p</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mi>q</mi>
  </mrow>
</math>.
Show that if we apply such a transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>T</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>p</mi>
      <mi>q</mi>
    </mrow>
  </msub>
</math> twice, the
effect is the same as using a single transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>T</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <msup>
        <mi>p</mi>
        <mo>′</mo>
      </msup>
      <msup>
        <mi>q</mi>
        <mo>′</mo>
      </msup>
    </mrow>
  </msub>
</math> of the
same form, and compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>p</mi>
    <mo>′</mo>
  </msup>
  <mspace width="negativethinmathspace"/>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>q</mi>
    <mo>′</mo>
  </msup>
  <mspace width="negativethinmathspace"/>
</math> in terms of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>p</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>q</mi>
</math>.  This
gives us an explicit way to square these transformations, and thus we can
compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>T</mi>
    <mi>n</mi>
  </msup>
</math> using successive squaring, as in the <code>fast-expt</code>
procedure.  Put this all together to complete the following procedure, which
runs in a logarithmic number of steps:<a class="footnote_link" id="DOCF41" href="#FOOT41"><sup>41</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fib-iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> n</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib-iter a b p q count</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> count </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
         b</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">even? count</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">fib-iter a
                   b
                   ⟨</span><span class="pun">??</span><span class="pln">⟩  </span><span class="com">;compute </span><var><span class="com">p'</span></var><span class="pln">
                   ⟨</span><span class="pun">??</span><span class="pln">⟩  </span><span class="com">;compute </span><var><span class="com">q'</span></var><span class="pln">
                   </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> count </span><span class="lit">2</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">fib-iter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b q</span><span class="clo">)</span><span class="pln"> 
                      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a q</span><span class="clo">)</span><span class="pln"> 
                      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a p</span><span class="clo">))</span><span class="pln">
                   </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b p</span><span class="clo">)</span><span class="pln"> 
                      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a q</span><span class="clo">))</span><span class="pln">
                   p
                   q
                   </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> count </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>
</blockquote>

<a id="g_t1_002e2_002e5"></a>
<a id="Greatest-Common-Divisors"></a>
<h4 class="subsection"><span class="secnum">1.2.5</span><span class="sectitle">Greatest Common Divisors</span></h4>

<p>The greatest common divisor (<abbr>GCD</abbr>) of two integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> is
defined to be the largest integer that divides both <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> with no
remainder.  For example, the <abbr>GCD</abbr> of 16 and 28 is 4.  In <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a>, when we investigate how to implement rational-number arithmetic, we will
need to be able to compute <abbr>GCD</abbr>s in order to reduce rational numbers
to lowest terms.  (To reduce a rational number to lowest terms, we must divide
both the numerator and the denominator by their <abbr>GCD</abbr>.  For example,
16/28 reduces to 4/7.)  One way to find the <abbr>GCD</abbr> of two integers is to
factor them and search for common factors, but there is a famous algorithm that
is much more efficient.
</p>
<p>The idea of the algorithm is based on the observation that, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>r</mi>
</math> is the
remainder when <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is divided by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, then the common divisors of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> are precisely the same as the common divisors of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>r</mi>
</math>.  Thus,
we can use the equation
</p>
<div class="example">
<pre class="example">GCD(a,b) = GCD(b,r)
</pre></div>

<p>to successively reduce the problem of computing a <abbr>GCD</abbr> to the problem
of computing the <abbr>GCD</abbr> of smaller and smaller pairs of integers.  For
example,
</p>
<div class="example">
<pre class="example">GCD(206,40) = GCD(40,6)
            = GCD(6,4)
            = GCD(4,2)
            = GCD(2,0) = 2
</pre></div>

<p>reduces <abbr>GCD</abbr>(206, 40) to <abbr>GCD</abbr>(2, 0), which is 2.  It is
possible to show that starting with any two positive integers and performing
repeated reductions will always eventually produce a pair where the second
number is 0.  Then the <abbr>GCD</abbr> is the other number in the pair.  This
method for computing the <abbr>GCD</abbr> is known as 
<a id="index-Euclid_0027s-Algorithm"></a>
<em>Euclid’s Algorithm</em>.<a class="footnote_link" id="DOCF42" href="#FOOT42"><sup>42</sup></a>
</p>
<p>It is easy to express Euclid’s Algorithm as a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> b </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      a
      </span><span class="opn">(</span><span class="pln">gcd b </span><span class="opn">(</span><span class="pln">remainder a b</span><span class="clo">))))</span></pre></div>

<p>This generates an iterative process, whose number of steps grows as the
logarithm of the numbers involved.
</p>
<p>The fact that the number of steps required by Euclid’s Algorithm has
logarithmic growth bears an interesting relation to the Fibonacci numbers:
</p>
<blockquote>
<p><strong>Lamé’s Theorem:</strong> If Euclid’s Algorithm requires <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> steps to
compute the <abbr>GCD</abbr> of some pair, then the smaller number in the pair
must be greater than or equal to the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> Fibonacci number.<a class="footnote_link" id="DOCF43" href="#FOOT43"><sup>43</sup></a>
</p></blockquote>

<p>We can use this theorem to get an order-of-growth estimate for Euclid’s
Algorithm.  Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> be the smaller of the two inputs to the procedure.  If
the process takes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> steps, then we must have 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
  <mo>≥<!-- ≥ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>≈<!-- ≈ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>φ<!-- φ --></mi>
      <mi>k</mi>
    </msup>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msqrt>
      <mn>5</mn>
    </msqrt>
  </mrow>
</math>.  Therefore the number of steps <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math>
grows as the logarithm (to the base <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
</math>) of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  Hence, the order of
growth is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e20"></a>Exercise 1.20:</strong> The process that a procedure
generates is of course dependent on the rules used by the interpreter.  As an
example, consider the iterative <code>gcd</code> procedure given above.  Suppose we
were to interpret this procedure using normal-order evaluation, as discussed in
<a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a>.  (The normal-order-evaluation rule for <code>if</code> is
described in <a href="1_002e1.xhtml#Exercise-1_002e5">Exercise 1.5</a>.)  Using the substitution method (for normal
order), illustrate the process generated in evaluating <code>(gcd 206 40)</code> and
indicate the <code>remainder</code> operations that are actually performed.  How many
<code>remainder</code> operations are actually performed in the normal-order
evaluation of <code>(gcd 206 40)</code>?  In the applicative-order evaluation?
</p></blockquote>

<a id="g_t1_002e2_002e6"></a>
<a id="Example_003a-Testing-for-Primality"></a>
<h4 class="subsection"><span class="secnum">1.2.6</span><span class="sectitle">Example: Testing for Primality</span></h4>

<p>This section describes two methods for checking the primality of an integer
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, one with order of growth <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msqrt>
      <mi>n</mi>
    </msqrt>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, and a
“probabilistic” algorithm with order of growth <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
The exercises at the end of this section suggest programming projects based on
these algorithms.
</p>
<a id="Searching-for-divisors"></a>
<h5 class="subsubheading">Searching for divisors</h5>

<p>Since ancient times, mathematicians have been fascinated by problems concerning
prime numbers, and many people have worked on the problem of determining ways
to test if numbers are prime.  One way to test if a number is prime is to find
the number’s divisors.  The following program finds the smallest integral
divisor (greater than 1) of a given number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  It does this in a
straightforward way, by testing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for divisibility by successive integers
starting with 2.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">smallest-divisor n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">find-divisor n </span><span class="lit">2</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">find-divisor n test-divisor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square test-divisor</span><span class="clo">)</span><span class="pln"> n</span><span class="clo">)</span><span class="pln"> 
         n</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">divides? test-divisor n</span><span class="clo">)</span><span class="pln"> 
         test-divisor</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">find-divisor 
               n 
               </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> test-divisor </span><span class="lit">1</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">divides? a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remainder b a</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>We can test whether a number is prime as follows: <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime if and only if
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is its own smallest divisor.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prime? n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">smallest-divisor n</span><span class="clo">)))</span></pre></div>

<p>The end test for <code>find-divisor</code> is based on the fact that if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is not
prime it must have a divisor less than or equal to
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>n</mi>
  </msqrt>
</math>.<a class="footnote_link" id="DOCF44" href="#FOOT44"><sup>44</sup></a>  This means that the algorithm need only test divisors
between 1 and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>n</mi>
  </msqrt>
</math>.  Consequently, the number of steps required
to identify <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> as prime will have order of growth
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msqrt>
      <mi>n</mi>
    </msqrt>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
</p>
<a id="The-Fermat-test"></a>
<h5 class="subsubheading">The Fermat test</h5>

<p>The <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> primality test is based on a result from
number theory known as Fermat’s Little Theorem.<a class="footnote_link" id="DOCF45" href="#FOOT45"><sup>45</sup></a>
</p>
<blockquote>
<p><strong>Fermat’s Little Theorem:</strong> If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is a prime number and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is any
positive integer less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> raised to the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> power is
congruent to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.
</p></blockquote>

<p>(Two numbers are said to be <a id="index-congruent-modulo"></a>
<em>congruent modulo</em> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> if they both have
the same remainder when divided by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  The remainder of a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> when
divided by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is also referred to as the <a id="index-remainder-of"></a>
<em>remainder of</em> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>
<a id="index-modulo"></a>
<em>modulo</em> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, or simply as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> <a id="index-modulo-1"></a>
<em>modulo</em> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.)
</p>
<p>If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is not prime, then, in general, most of the numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> will
not satisfy the above relation.  This leads to the following algorithm for
testing primality: Given a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, pick a random number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> and
compute the remainder of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>a</mi>
    <mi>n</mi>
  </msup>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  If the result is not equal
to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is certainly not prime.  If it is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, then chances are
good that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  Now pick another random number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and test it
with the same method.  If it also satisfies the equation, then we can be even
more confident that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  By trying more and more values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>,
we can increase our confidence in the result.  This algorithm is known as the
Fermat test.
</p>
<p>To implement the Fermat test, we need a procedure that computes the exponential
of a number modulo another number:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expmod base exp m</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> exp </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">even? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">remainder 
          </span><span class="opn">(</span><span class="pln">square </span><span class="opn">(</span><span class="pln">expmod base </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> exp </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">))</span><span class="pln">
          m</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">remainder 
          </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> base </span><span class="opn">(</span><span class="pln">expmod base </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> exp </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">))</span><span class="pln">
          m</span><span class="clo">))))</span></pre></div>

<p>This is very similar to the <code>fast-expt</code> procedure of <a href="#g_t1_002e2_002e4">1.2.4</a>.
It uses successive squaring, so that the number of steps grows logarithmically
with the exponent.<a class="footnote_link" id="DOCF46" href="#FOOT46"><sup>46</sup></a>
</p>
<p>The Fermat test is performed by choosing at random a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> between 1 and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> inclusive and checking whether the remainder modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> of the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> power of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is equal to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>.  The random number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is chosen
using the procedure <code>random</code>, which we assume is included as a primitive
in Scheme. <code>Random</code> returns a nonnegative integer less than its integer
input.  Hence, to obtain a random number between 1 and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math>, we call
<code>random</code> with an input of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> and add 1 to the result:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fermat-test n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">try-it a</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expmod a n n</span><span class="clo">)</span><span class="pln"> a</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">try-it </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">random </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

<p>The following procedure runs the test a given number of times, as specified by
a parameter.  Its value is true if the test succeeds every time, and false
otherwise.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fast-prime? n times</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> times </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">fermat-test n</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">fast-prime? n </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> times </span><span class="lit">1</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> false</span><span class="clo">)))</span></pre></div>

<a id="Probabilistic-methods"></a>
<h5 class="subsubheading">Probabilistic methods</h5>

<p>The Fermat test differs in character from most familiar algorithms, in which
one computes an answer that is guaranteed to be correct.  Here, the answer
obtained is only probably correct.  More precisely, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> ever fails the
Fermat test, we can be certain that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is not prime.  But the fact that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> passes the test, while an extremely strong indication, is still not a
guarantee that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  What we would like to say is that for any
number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, if we perform the test enough times and find that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> always
passes the test, then the probability of error in our primality test can be
made as small as we like.
</p>
<p>Unfortunately, this assertion is not quite correct.  There do exist numbers
that fool the Fermat test: numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> that are not prime and yet have the
property that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>a</mi>
    <mi>n</mi>
  </msup>
</math> is congruent to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for all integers
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math>.  Such numbers are extremely rare, so the Fermat test is quite
reliable in practice.<a class="footnote_link" id="DOCF47" href="#FOOT47"><sup>47</sup></a>
</p>
<p>There are variations of the Fermat test that cannot be fooled.  In these tests,
as with the Fermat method, one tests the primality of an integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> by
choosing a random integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> and checking some condition that depends
upon <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>.  (See <a href="#Exercise-1_002e28">Exercise 1.28</a> for an example of such a test.)
On the other hand, in contrast to the Fermat test, one can prove that, for any
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, the condition does not hold for most of the integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> unless
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  Thus, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> passes the test for some random choice of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, the chances are better than even that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> passes
the test for two random choices of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, the chances are better than 3 out of
4 that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime. By running the test with more and more randomly chosen
values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> we can make the probability of error as small as we like.
</p>
<p>The existence of tests for which one can prove that the chance of error becomes
arbitrarily small has sparked interest in algorithms of this type, which have
come to be known as <a id="index-probabilistic-algorithms"></a>
<em>probabilistic algorithms</em>.  There is a great deal
of research activity in this area, and probabilistic algorithms have been
fruitfully applied to many fields.<a class="footnote_link" id="DOCF48" href="#FOOT48"><sup>48</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e21"></a>Exercise 1.21:</strong> Use the <code>smallest-divisor</code>
procedure to find the smallest divisor of each of the following numbers: 199,
1999, 19999.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e22"></a>Exercise 1.22:</strong> Most Lisp implementations include
a primitive called <code>runtime</code> that returns an integer that specifies the
amount of time the system has been running (measured, for example, in
microseconds).  The following <code>timed-prime-test</code> procedure, when called
with an integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, prints <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and checks to see if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime.  If
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime, the procedure prints three asterisks followed by the amount of
time used in performing the test.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">timed-prime-test n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">start-prime-test n </span><span class="opn">(</span><span class="pln">runtime</span><span class="clo">)))</span></pre></div>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">start-prime-test n start-time</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prime? n</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">report-prime </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">runtime</span><span class="clo">)</span><span class="pln"> 
                       start-time</span><span class="clo">))))</span></pre></div>

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">report-prime elapsed-time</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display </span><span class="str">" *** "</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display elapsed-time</span><span class="clo">))</span></pre></div>

<p>Using this procedure, write a procedure <code>search-for-primes</code> that checks
the primality of consecutive odd integers in a specified range.  Use your
procedure to find the three smallest primes larger than 1000; larger than
10,000; larger than 100,000; larger than 1,000,000.  Note the time needed to
test each prime.  Since the testing algorithm has order of growth of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msqrt>
      <mi>n</mi>
    </msqrt>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, you should expect that testing for primes
around 10,000 should take about <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mn>10</mn>
  </msqrt>
</math> times as long as testing for
primes around 1000.  Do your timing data bear this out?  How well do the data
for 100,000 and 1,000,000 support the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <msqrt>
      <mi>n</mi>
    </msqrt>
    <mo stretchy="false">)</mo>
  </mrow>
</math> prediction?  Is your
result compatible with the notion that programs on your machine run in time
proportional to the number of steps required for the computation?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e23"></a>Exercise 1.23:</strong> The <code>smallest-divisor</code>
procedure shown at the start of this section does lots of needless testing:
After it checks to see if the number is divisible by 2 there is no point in
checking to see if it is divisible by any larger even numbers.  This suggests
that the values used for <code>test-divisor</code> should not be 2, 3, 4, 5, 6,
…, but rather 2, 3, 5, 7, 9, ….  To implement this change, define a
procedure <code>next</code> that returns 3 if its input is equal to 2 and otherwise
returns its input plus 2.  Modify the <code>smallest-divisor</code> procedure to use
<code>(next test-divisor)</code> instead of <code>(+ test-divisor 1)</code>.  With
<code>timed-prime-test</code> incorporating this modified version of
<code>smallest-divisor</code>, run the test for each of the 12 primes found in
<a href="#Exercise-1_002e22">Exercise 1.22</a>.  Since this modification halves the number of test steps,
you should expect it to run about twice as fast.  Is this expectation
confirmed?  If not, what is the observed ratio of the speeds of the two
algorithms, and how do you explain the fact that it is different from 2?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e24"></a>Exercise 1.24:</strong> Modify the
<code>timed-prime-test</code> procedure of <a href="#Exercise-1_002e22">Exercise 1.22</a> to use
<code>fast-prime?</code> (the Fermat method), and test each of the 12 primes you
found in that exercise.  Since the Fermat test has <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
growth, how would you expect the time to test primes near 1,000,000 to
compare with the time needed to test primes near 1000?  Do your data bear this
out?  Can you explain any discrepancy you find?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e25"></a>Exercise 1.25:</strong> Alyssa P. Hacker complains that
we went to a lot of extra work in writing <code>expmod</code>.  After all, she says,
since we already know how to compute exponentials, we could have simply written
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expmod base exp m</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">remainder </span><span class="opn">(</span><span class="pln">fast-expt base exp</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">))</span></pre></div>

<p>Is she correct?  Would this procedure serve as well for our fast prime tester?
Explain.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e26"></a>Exercise 1.26:</strong> Louis Reasoner is having great
difficulty doing <a href="#Exercise-1_002e24">Exercise 1.24</a>.  His <code>fast-prime?</code> test seems to run
more slowly than his <code>prime?</code> test.  Louis calls his friend Eva Lu Ator
over to help.  When they examine Louis’s code, they find that he has rewritten
the <code>expmod</code> procedure to use an explicit multiplication, rather than
calling <code>square</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expmod base exp m</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">=</span><span class="pln"> exp </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">even? exp</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">remainder 
          </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expmod base </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> exp </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">expmod base </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> exp </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">))</span><span class="pln">
          m</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">remainder 
          </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> base 
             </span><span class="opn">(</span><span class="pln">expmod base </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> exp </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> m</span><span class="clo">))</span><span class="pln">
          m</span><span class="clo">))))</span></pre></div>

<p>“I don’t see what difference that could make,” says Louis.  “I do.”<!-- /@w -->  says
Eva.  “By writing the procedure like that, you have transformed the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> process into a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> process.”
Explain.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e27"></a>Exercise 1.27:</strong> Demonstrate that the Carmichael
numbers listed in <a href="#Footnote-47">Footnote 47</a> really do fool the Fermat test.  That is,
write a procedure that takes an integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and tests whether <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>a</mi>
    <mi>n</mi>
  </msup>
</math> is
congruent to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> for every <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math>, and try your procedure
on the given Carmichael numbers.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e28"></a>Exercise 1.28:</strong> One variant of the Fermat test
that cannot be fooled is called the <a id="index-Miller_002dRabin-test"></a>
<em>Miller-Rabin test</em> (<a href="References.xhtml#Miller-1976">Miller 1976</a>;
<a href="References.xhtml#Rabin-1980">Rabin 1980</a>).  This starts from an alternate form of Fermat’s Little Theorem,
which states that if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is a prime number and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> is any positive integer
less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> raised to the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>-st power is congruent to 1
modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  To test the primality of a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> by the Miller-Rabin
test, we pick a random number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> and raise <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> to the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>-st
power modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> using the <code>expmod</code> procedure.  However, whenever we
perform the squaring step in <code>expmod</code>, we check to see if we have
discovered a “nontrivial square root of 1 modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>,” that is, a number
not equal to 1 or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> whose square is equal to 1 modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  It is
possible to prove that if such a nontrivial square root of 1 exists, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>
is not prime.  It is also possible to prove that if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is an odd number that
is not prime, then, for at least half the numbers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math>, computing
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>a</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msup>
</math> in this way will reveal a nontrivial square root of 1 modulo
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  (This is why the Miller-Rabin test cannot be fooled.)  Modify the
<code>expmod</code> procedure to signal if it discovers a nontrivial square root of
1, and use this to implement the Miller-Rabin test with a procedure analogous
to <code>fermat-test</code>.  Check your procedure by testing various known primes
and non-primes.  Hint: One convenient way to make <code>expmod</code> signal is to
have it return 0.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT29"><p><a class="footnote_backlink" href="#DOCF29"><sup>29</sup></a>
In a real program we would probably use the block
structure introduced in the last section to hide the definition of
<code>fact-iter</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter product counter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>We avoided doing this here so as to minimize the number of things to think
about at once.</p>
</div>
<div id="FOOT30"><p><a class="footnote_backlink" href="#DOCF30"><sup>30</sup></a>
When we discuss the implementation of procedures on
register machines in <a href="Chapter-5.xhtml#Chapter-5">Chapter 5</a>, we will see that any iterative process
can be realized “in hardware” as a machine that has a fixed set of registers
and no auxiliary memory.  In contrast, realizing a recursive process requires a
machine that uses an auxiliary data structure known as a <a id="index-stack"></a>
<em>stack</em>.</p>
</div>
<div id="FOOT31"><p><a class="footnote_backlink" href="#DOCF31"><sup>31</sup></a>
Tail
recursion has long been known as a compiler optimization trick.  A coherent
semantic basis for tail recursion was provided by Carl <a href="References.xhtml#Hewitt-_00281977_0029">Hewitt (1977)</a>, who
explained it in terms of the “message-passing” model of computation that we
shall discuss in <a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.  Inspired by this, Gerald Jay Sussman and Guy
Lewis Steele Jr. (see <a href="References.xhtml#Steele-and-Sussman-1975">Steele and Sussman 1975</a>) constructed a tail-recursive interpreter for
Scheme.  Steele later showed how tail recursion is a consequence of the natural
way to compile procedure calls (<a href="References.xhtml#Steele-1977">Steele 1977</a>).  The <abbr>IEEE</abbr> standard for
Scheme requires that Scheme implementations be tail-recursive.</p>
</div>
<div id="FOOT32"><p><a class="footnote_backlink" href="#DOCF32"><sup>32</sup></a>
An example of this was hinted at in <a href="1_002e1.xhtml#g_t1_002e1_002e3">1.1.3</a>. The
interpreter itself evaluates expressions using a tree-recursive process.</p>
</div>
<div id="FOOT33"><p><a class="footnote_backlink" href="#DOCF33"><sup>33</sup></a>
For
example, work through in detail how the reduction rule applies to the problem
of making change for 10 cents using pennies and nickels.</p>
</div>
<div id="FOOT34"><p><a class="footnote_backlink" href="#DOCF34"><sup>34</sup></a>
One approach to coping with
redundant computations is to arrange matters so that we automatically construct
a table of values as they are computed.  Each time we are asked to apply the
procedure to some argument, we first look to see if the value is already stored
in the table, in which case we avoid performing the redundant computation.
This strategy, known as <a id="index-tabulation"></a>
<em>tabulation</em> or <a id="index-memoization"></a>
<em>memoization</em>, can be
implemented in a straightforward way.  Tabulation can sometimes be used to
transform processes that require an exponential number of steps (such as
<code>count-change</code>) into processes whose space and time requirements grow
linearly with the input.  See <a href="3_002e3.xhtml#Exercise-3_002e27">Exercise 3.27</a>.</p>
</div>
<div id="FOOT35"><p><a class="footnote_backlink" href="#DOCF35"><sup>35</sup></a>
The elements of
Pascal’s triangle are called the <a id="index-binomial-coefficients"></a>
<em>binomial coefficients</em>, because the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>n</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mtext>th</mtext>
      </mrow>
    </msup>
  </mrow>
</math> row consists of the coefficients of the terms in the expansion of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>+</mo>
    <mi>y</mi>
    <msup>
      <mo stretchy="false">)</mo>
      <mi>n</mi>
    </msup>
  </mrow>
</math>.  This pattern for computing the coefficients appeared in
Blaise Pascal’s 1653 seminal work on probability theory, <cite>Traité du
triangle arithmétique</cite>.  According to <a href="References.xhtml#Knuth-_00281973_0029">Knuth (1973)</a>, the same pattern appears
in the <cite>Szu-yuen Yü-chien</cite> (“The Precious Mirror of the Four
Elements”), published by the Chinese mathematician Chu Shih-chieh in 1303, in
the works of the twelfth-century Persian poet and mathematician Omar Khayyam,
and in the works of the twelfth-century Hindu mathematician Bháscara
Áchárya.</p>
</div>
<div id="FOOT36"><p><a class="footnote_backlink" href="#DOCF36"><sup>36</sup></a>
These statements mask a great deal of oversimplification.
For instance, if we count process steps as “machine operations” we are making
the assumption that the number of machine operations needed to perform, say, a
multiplication is independent of the size of the numbers to be multiplied,
which is false if the numbers are sufficiently large.  Similar remarks hold for
the estimates of space.  Like the design and description of a process, the
analysis of a process can be carried out at various levels of abstraction.</p>
</div>
<div id="FOOT37"><p><a class="footnote_backlink" href="#DOCF37"><sup>37</sup></a>
More precisely, the number of
multiplications required is equal to 1 less than the log base 2 of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> plus
the number of ones in the binary representation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  This total is always
less than twice the log base 2 of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  The arbitrary constants <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>k</mi>
    <mn>1</mn>
  </msub>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>k</mi>
    <mn>2</mn>
  </msub>
</math> in the definition of order notation imply that, for a logarithmic
process, the base to which logarithms are taken does not matter, so all such
processes are described as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.</p>
</div>
<div id="FOOT38"><p><a class="footnote_backlink" href="#DOCF38"><sup>38</sup></a>
You may wonder why anyone would care about raising
numbers to the 1000th power.  See <a href="#g_t1_002e2_002e6">1.2.6</a>.</p>
</div>
<div id="FOOT39"><p><a class="footnote_backlink" href="#DOCF39"><sup>39</sup></a>
This
iterative algorithm is ancient.  It appears in the <cite>Chandah-sutra</cite> by
Áchárya Pingala, written before 200 <abbr>B.C.</abbr> See <a href="References.xhtml#Knuth-1981">Knuth 1981</a>, section
4.6.3, for a full discussion and analysis of this and other methods of
exponentiation.</p>
</div>
<div id="FOOT40"><p><a class="footnote_backlink" href="#DOCF40"><sup>40</sup></a>
This algorithm,
which is sometimes known as the “Russian peasant method” of multiplication,
is ancient.  Examples of its use are found in the Rhind Papyrus, one of the two
oldest mathematical documents in existence, written about 1700 <abbr>B.C.</abbr>
(and copied from an even older document) by an Egyptian scribe named A’h-mose.</p>
</div>
<div id="FOOT41"><p><a class="footnote_backlink" href="#DOCF41"><sup>41</sup></a>
This exercise was suggested to
us by Joe Stoy, based on an example in <a href="References.xhtml#Kaldewaij-1990">Kaldewaij 1990</a>.</p>
</div>
<div id="FOOT42"><p><a class="footnote_backlink" href="#DOCF42"><sup>42</sup></a>
Euclid’s Algorithm is so called because 
it appears in Euclid’s <cite>Elements</cite> (Book 7, ca. 300 <abbr>B.C.</abbr>).  
According to <a href="References.xhtml#Knuth-_00281973_0029">Knuth (1973)</a>, it can be considered the oldest known nontrivial 
algorithm.  The ancient Egyptian method of multiplication (<a href="#Exercise-1_002e18">Exercise 1.18</a>) is 
surely older, but, as Knuth explains, Euclid’s algorithm is the oldest known to 
have been presented as a general algorithm, rather than as a set of illustrative
examples.</p>
</div>
<div id="FOOT43"><p><a class="footnote_backlink" href="#DOCF43"><sup>43</sup></a>
This
theorem was proved in 1845 by Gabriel Lamé, a French mathematician and
engineer known chiefly for his contributions to mathematical physics.  To prove
the theorem, we consider pairs <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mi>k</mi>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mi>k</mi>
    </msub>
    <mo>≥<!-- ≥ --></mo>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
  </mrow>
</math>, 
for which Euclid’s Algorithm terminates in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> steps.  The proof
is based on the claim that, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo stretchy="false">→<!-- → --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mi>k</mi>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo stretchy="false">→<!-- → --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> 
are three successive pairs 
in the reduction process, then we must have <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
  <mo>+</mo>
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
</math>.  
To verify the claim, consider that a reduction step is defined by applying the 
transformation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>=</mo>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>=</mo>
  </mrow>
</math> remainder of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mi>k</mi>
  </msub>
</math> 
divided by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
</math>.  The second equation means that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mi>k</mi>
  </msub>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>q</mi>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
  </mrow>
</math> 
for some positive integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>q</mi>
</math>.  And since <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>q</mi>
</math> must be at least 1 we have 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mi>k</mi>
  </msub>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>q</mi>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
  </mrow>
  <mo>+</mo>
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
  <mo>+</mo>
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
</math>.  But in the previous reduction 
step we have <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>=</mo>
  <msub>
    <mi>a</mi>
    <mi>k</mi>
  </msub>
</math>.  Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>=</mo>
  <msub>
    <mi>a</mi>
    <mi>k</mi>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
  <mo>+</mo>
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
</math>.
This verifies the claim.  Now we can prove the theorem by induction on <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math>, 
the number of steps that the algorithm requires to terminate.  The result is true for 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>, since this merely requires that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> be at least as large as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>.  
Now, assume that the result is true for all integers less than or equal
to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math> and establish the result for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>k</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math>.  
Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo stretchy="false">→<!-- → --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mi>k</mi>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo stretchy="false">→<!-- → --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>a</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>b</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>k</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> 
be successive pairs in the reduction 
process.  By our induction hypotheses, we have <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> 
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  Thus, applying the claim we just proved together with 
the definition of the Fibonacci numbers gives 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <msub>
    <mi>b</mi>
    <mi>k</mi>
  </msub>
  <mo>+</mo>
  <msub>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>k</mi>
      <mo>−<!-- − --></mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≥<!-- ≥ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>k</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, 
which completes the proof of Lamé’s Theorem.</p>
</div>
<div id="FOOT44"><p><a class="footnote_backlink" href="#DOCF44"><sup>44</sup></a>
If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math> is a divisor of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, then so is
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>d</mi>
  </mrow>
</math>.  But <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>d</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>d</mi>
  </mrow>
</math> cannot both be greater than
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>n</mi>
  </msqrt>
</math>.</p>
</div>
<div id="FOOT45"><p><a class="footnote_backlink" href="#DOCF45"><sup>45</sup></a>
Pierre de Fermat
(1601-1665) is considered to be the founder of modern number theory.  He
obtained many important number-theoretic results, but he usually announced just
the results, without providing his proofs.  Fermat’s Little Theorem was stated
in a letter he wrote in 1640.  The first published proof was given by Euler in
1736 (and an earlier, identical proof was discovered in the unpublished
manuscripts of Leibniz).  The most famous of Fermat’s results—known as
Fermat’s Last Theorem—was jotted down in 1637 in his copy of the book
<cite>Arithmetic</cite> (by the third-century Greek mathematician Diophantus) with
the remark “I have discovered a truly remarkable proof, but this margin is too
small to contain it.”  Finding a proof of Fermat’s Last Theorem became one of
the most famous challenges in number theory.  A complete solution was finally
given in 1995 by Andrew Wiles of Princeton University.</p>
</div>
<div id="FOOT46"><p><a class="footnote_backlink" href="#DOCF46"><sup>46</sup></a>
The reduction steps in the cases where the exponent
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>e</mi>
</math> is greater than 1 are based on the fact that, for any integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>, we can find the remainder of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> times <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>
by computing separately the remainders of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> modulo
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>, multiplying these, and then taking the remainder of the result modulo
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>.  For instance, in the case where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>e</mi>
</math> is even, we compute the remainder
of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>b</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>e</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mo>/</mo>
      </mrow>
      <mn>2</mn>
    </mrow>
  </msup>
</math> modulo <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>, square this, and take the remainder modulo
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>.  This technique is useful because it means we can perform our
computation without ever having to deal with numbers much larger than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math>.
(Compare <a href="#Exercise-1_002e25">Exercise 1.25</a>.)</p>
</div>
<div id="FOOT47"><p><a class="footnote_backlink" href="#DOCF47"><sup>47</sup></a>
<a id="Footnote-47"></a>Numbers
that fool the Fermat test are called <a id="index-Carmichael-numbers"></a>
<em>Carmichael numbers</em>, and little
is known about them other than that they are extremely rare.  There are 255
Carmichael numbers below 100,000,000.  The smallest few are 561, 1105, 1729,
2465, 2821, and 6601.  In testing primality of very large numbers chosen at
random, the chance of stumbling upon a value that fools the Fermat test is less
than the chance that cosmic radiation will cause the computer to make an error
in carrying out a “correct” algorithm.  Considering an algorithm to be
inadequate for the first reason but not for the second illustrates the
difference between mathematics and engineering.</p>
</div>
<div id="FOOT48"><p><a class="footnote_backlink" href="#DOCF48"><sup>48</sup></a>
One of the most striking
applications of probabilistic prime testing has been to the field of
cryptography.  Although it is now computationally infeasible to factor an
arbitrary 200-digit number, the primality of such a number can be checked in a
few seconds with the Fermat test.  This fact forms the basis of a technique for
constructing “unbreakable codes” suggested by <a href="References.xhtml#Rivest-et-al_002e-_00281977_0029">Rivest et al. (1977)</a>.  
The resulting <a id="index-RSA-algorithm"></a>
<em>RSA algorithm</em> has become a widely used
technique for enhancing the security of electronic communications.  Because of
this and related developments, the study of prime numbers, once considered the
epitome of a topic in “pure” mathematics to be studied only for its own sake,
now turns out to have important practical applications to cryptography,
electronic funds transfer, and information retrieval.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="1_002e3.xhtml#g_t1_002e3" accesskey="n" rel="next">1.3</a>, Prev: <a href="1_002e1.xhtml#g_t1_002e1" accesskey="p" rel="prev">1.1</a>, Up: <a href="#g_t1_002e2" accesskey="u" rel="prev">1.2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>